package 代码随想录_回溯.组合;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zx
 * @create 2022-06-09 10:40
 */
public class 组合求和_39 {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,target,0,0);
        return res;
    }
    private void dfs(int[] candidates,int target,int sum,int startIndex){
        if(sum > target){
            return;
        }
        if(sum == target){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = startIndex;i < candidates.length;i++){
            sum += candidates[i];
            list.add(candidates[i]);
            dfs(candidates,target,sum,i);//不用i+1了,表示可以重复读取当前的数
            //回溯
            sum -= candidates[i];
            list.removeLast();
        }
    }
}
class combinationSumway2{
    /**
     * @return  剪枝优化
     * 在求和问题中,排序之后加剪枝是常见的套路！
     *
     * 对于sum已经大于target的情况,其实是依然进入了下一层递归,只是下一层递归结束判断的时候,会判断sum > target的话就返回
     * 其实如果已经知道下一层的sum会大于target,就没有必要进入下一层递归了
     * 对总集合排序之后,如果下一层的sum(就是本层的sum + candidates[i])已经大于target,就可以结束本轮for循环的遍历
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);// 需要排序
        dfs(candidates,target,0,0);
        return res;
    }
    List<List<Integer>> res = new ArrayList<>();

    LinkedList<Integer> list = new LinkedList<>();
    private void dfs(int[] candidates,int target,int sum,int startIndex){
        if(sum > target){
            return;
        }
        if(sum == target){
            res.add(new ArrayList<>(list));
            return;
        }
        //如果 sum + candidates[i] > target 就终止遍历
        for(int i = startIndex;i < candidates.length && sum + candidates[i] <= target;i++){
            sum += candidates[i];
            list.add(candidates[i]);
            dfs(candidates,target,sum,i); //不用i+1了,表示可以重复读取当前的数
            //回溯
            sum -= candidates[i];
            list.removeLast();
        }
    }
}
